#include "abb.h"
#include "pila.h"
#include "cola.h"
#include <stdlib.h>
#include <string.h>


typedef struct hoja hoja_t;

bool destruir_abb = false;

struct hoja{
	char *clave;
	void *valor;
	hoja_t* izq, *der;
};

struct abb{
	hoja_t* raiz;
	size_t cant;
	abb_destruir_dato_t destruir_dato;
	abb_comparar_clave_t cmp;
};

struct abb_iter{
	const abb_t* arbol;
	cola_t* hojas;
	hoja_t* hoja_actual;
};

struct info_hojas_abb{
	hoja_t* hoja_anterior;
	hoja_t* hoja_actual;
	int direccion;
};

typedef struct info_hojas_abb info_hojas_abb;

char *strdup(const char *str)
{
    int n = strlen(str) + 1;
    char *dup = malloc(sizeof(char)*n);
    if(dup)
    {
        strcpy(dup, str);
    }
    return dup;
}

hoja_t* hoja_crear(const char *clave, void *dato)
{
	hoja_t* hoja = malloc(sizeof(hoja_t));
	if (!hoja) return false;

	hoja->clave = strdup(clave);
	if (!hoja->clave)
	{
		free(hoja);
		return false;
	}
	hoja->valor = dato;
	hoja->izq = hoja->der = NULL;
	
	return hoja;
}

void hoja_destruir(hoja_t* hoja, const abb_t* arbol)
{
	if (!arbol || !hoja) return;
	if (destruir_abb && arbol->destruir_dato) arbol->destruir_dato(hoja->valor);
	free(hoja->clave);
	free(hoja);
}

info_hojas_abb hoja_obtener(const abb_t* arbol, const char*clave)
/* Devuelve un vector de void*, con 3 componentes:  la hoja anterior, la buscada o NULL si no pertenece, y
   1 o -1 según la hoja hijo este a la izquierda o derecha del padre */
{
	
	info_hojas_abb info_hojas = {NULL, NULL, 0};

	if (!arbol) return info_hojas;
	if (!arbol->raiz) return info_hojas;

	int hoja_direccion;
	hoja_t* hoja_actual = arbol->raiz;

	info_hojas.hoja_actual = hoja_actual;

	while (info_hojas.hoja_actual)
	{
		hoja_direccion = arbol->cmp(info_hojas.hoja_actual->clave, clave);
		if (hoja_direccion == 0){
			return info_hojas;
		}

		info_hojas.hoja_anterior = info_hojas.hoja_actual;
		if (hoja_direccion >= 1)
		{
			info_hojas.hoja_actual = info_hojas.hoja_anterior->izq;
			info_hojas.direccion = 1;
		}else
		{
			info_hojas.hoja_actual = info_hojas.hoja_anterior->der;
			info_hojas.direccion = -1;
		}
	}
	return info_hojas;
}

void hoja_in_order(hoja_t* hoja, bool funcion(const char *, void *, void *), void *extra)
{
	if (!hoja) return;
	
	hoja_in_order(hoja->izq, funcion, extra);
	funcion(hoja->clave, hoja->valor, extra);
	hoja_in_order(hoja->der, funcion, extra);
}

hoja_t* buscar_hijo(hoja_t* padre){
	if (padre->izq){
		return padre->izq;
	} else {
		return padre->der;
	}
}

info_hojas_abb buscar_sucesor(hoja_t* hoja_actual){
/* Devuelve en un struct info_hojas el sucesor de una hoja en hoja actual,
 * el padre del sucesor en hoja anterior, y la direccion del padre hacia el hijo.
   Por sucesor se entiende el siguiente nodo in-order */

	hoja_t* nodo_derecho = hoja_actual->der;

	info_hojas_abb info_hojas = {hoja_actual, nodo_derecho, -1};

	if (!nodo_derecho->izq) return info_hojas;

	hoja_t* sucesor = nodo_derecho->izq;
	hoja_t* padre_sucesor = nodo_derecho;

	while (sucesor->izq){
		padre_sucesor = sucesor;
		sucesor = sucesor->izq;
	}
	info_hojas.hoja_anterior = padre_sucesor;
	info_hojas.hoja_actual = sucesor;
	info_hojas.direccion = 1;
	return info_hojas;
}

void abb_reemplazar(hoja_t* actual, hoja_t* sucesor){
	
	char* aux_clave = actual->clave;
	void* aux_valor = actual->valor;

	actual->clave = sucesor->clave;
	actual->valor = sucesor->valor;

	sucesor->clave = aux_clave;
	sucesor->valor = aux_valor;
}

abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato)
{
	if (!cmp) return NULL;
	abb_t* arbol = malloc(sizeof(abb_t));
	if (!arbol) return NULL;
	
	arbol->cant = 0;
	arbol->raiz = NULL;
	arbol->cmp = cmp;
	arbol->destruir_dato = destruir_dato;
	
	return arbol;
}

size_t abb_cantidad(abb_t *arbol)
{
	if (!arbol) return 0;
	return arbol->cant;
}

bool abb_guardar(abb_t *arbol, const char *clave, void *dato)
{
	if (!arbol) return false;
	if (!clave) return false;
	info_hojas_abb info_hojas = hoja_obtener(arbol, clave);
	if (info_hojas.hoja_actual)
	{
		if (arbol->destruir_dato) arbol->destruir_dato(info_hojas.hoja_actual->valor);
		info_hojas.hoja_actual->valor = dato;
		return true;
	}

	hoja_t* hoja = hoja_crear(clave, dato);
	if (!hoja) return false;

	if (!arbol->raiz)
	{
		arbol->raiz = hoja;
		arbol->cant++;
	} else {
		arbol->cant++;
		hoja_t* hoja_agregar = info_hojas.hoja_anterior;
		int hoja_direccion = arbol->cmp(hoja_agregar->clave, clave);
		if (hoja_direccion <= -1)
		{
			hoja_agregar->der = hoja;
		} else {
			hoja_agregar->izq = hoja;
		}
	}
	
	return true;
}

void *abb_obtener(const abb_t *arbol, const char *clave)
{
	hoja_t* hoja = hoja_obtener(arbol, clave).hoja_actual;
	if (!hoja) return NULL;
	return hoja->valor;	
}

bool abb_pertenece(const abb_t *arbol, const char *clave)
{
	hoja_t* hoja = hoja_obtener(arbol, clave).hoja_actual;
	if (hoja) return true;
	return false;
}

void* borrar(abb_t* arbol, info_hojas_abb info_hojas){

		hoja_t* hijo = buscar_hijo(info_hojas.hoja_actual); 
		hoja_t* aux = hijo;
		void* valor = info_hojas.hoja_actual->valor;
		free(info_hojas.hoja_actual->clave); free(info_hojas.hoja_actual);
		arbol->cant--;
		if (info_hojas.direccion >= 1){
			info_hojas.hoja_anterior->izq = aux;
		} else if (info_hojas.direccion <= -1){
			info_hojas.hoja_anterior->der = aux;
		} else if (info_hojas.direccion == 0) { // Se esta borrando la raiz
			arbol->raiz = aux;
		}
		return valor;
}

void *abb_borrar(abb_t *arbol, const char *clave)
{
	if (!arbol) return NULL;
	if (!arbol->raiz) return NULL;

	info_hojas_abb info_hojas = hoja_obtener(arbol, clave);

	if (!info_hojas.hoja_actual) return NULL; // El elemento a borrar no pertenece al ABB

	void* valor;
	
	// Caso borrar un nodo con 1 solo subarbol hijo o ninguno
	if(!info_hojas.hoja_actual->izq || !info_hojas.hoja_actual->der){ 
		valor = borrar(arbol, info_hojas);
	}else{
		// Caso borrar un nodo con 2 subarboles hijos
		// Se swapea el actual con el sucesor y se reduce al caso anterior
		info_hojas_abb info_hojas_sucesor = buscar_sucesor(info_hojas.hoja_actual); 
		abb_reemplazar(info_hojas.hoja_actual, info_hojas_sucesor.hoja_actual);
		valor = borrar(arbol, info_hojas_sucesor);
		}
	return valor;
}

void abb_destruir(abb_t *arbol)
{
	if (!arbol) return	;
	
	pila_t* pila = pila_crear();
	
	destruir_abb = true;
	
	hoja_t* hoja_actual = arbol->raiz;
	while(hoja_actual)	// Este while tiene como condicion hoja_actual por si arbol->raiz es NULL
	{
		if (hoja_actual->izq || hoja_actual->der)
		{	// Apila solo los elementos que tienen hijos.
			pila_apilar(pila, hoja_actual);
			// Luego avanza al proximo elemento.
			if (hoja_actual->izq)
			{
				hoja_actual = hoja_actual->izq;
			} else {
				hoja_actual = hoja_actual->der;
			}
		} else {
			// Si no tiene hijos destruye el elemento.
			hoja_destruir(hoja_actual, arbol);
			if (pila_esta_vacia(pila)) break;
			// y desapila el anterior.
			hoja_actual = pila_desapilar(pila);
			if (hoja_actual->izq)
			{	// Esto para que la hoja anterior no siga guardando referencia a la hoja borrada.
				hoja_actual->izq = NULL;
			} else {
				hoja_actual->der = NULL;
			}
		}
	}
	pila_destruir(pila);
	free(arbol);
}

void abb_in_order(abb_t *arbol, bool funcion(const char *, void *, void *), void *extra)
{
	if (!arbol) return;
	if (!funcion) return; // Ya que no tendria sentido recorrer el arbol si no se va a hacer nada con sus elementos
	
	hoja_in_order(arbol->raiz, funcion, extra);
}

bool callback_cola(const char* clave, void* valor, cola_t* cola)
{
	hoja_t* hoja = hoja_crear(clave, valor);
	if (!hoja) return false;
	
	return cola_encolar(cola, hoja);
}

abb_iter_t *abb_iter_in_crear(const abb_t *arbol)
{
	if (!arbol) return NULL;
	abb_iter_t* iter = malloc(sizeof(abb_iter_t));
	if (!iter) return NULL;
	
	cola_t* cola = cola_crear();
	if (!cola)
	{
		free(iter);
		return NULL;
	}
	
	iter->hojas = cola;
	abb_in_order((abb_t*) arbol, (_Bool (*)(const char *, void *, void *))callback_cola, cola);
	iter->hoja_actual = cola_desencolar(iter->hojas);
	iter->arbol = arbol;
	return iter;
}

bool abb_iter_in_al_final(const abb_iter_t *iter)
{
	if (!iter) return true;
	if (!iter->hoja_actual) return true;
	return false;
}

bool abb_iter_in_avanzar(abb_iter_t *iter)
{
	if (!iter) return false;
	if (abb_iter_in_al_final(iter)) return false;
	hoja_destruir(iter->hoja_actual, iter->arbol);
	iter->hoja_actual = cola_desencolar(iter->hojas);
	return true;
}

const char *abb_iter_in_ver_actual(const abb_iter_t *iter)
{
	if(!iter) return NULL;
	if (abb_iter_in_al_final(iter)) return NULL;
	return iter->hoja_actual->clave;
}

void abb_iter_in_destruir(abb_iter_t* iter)
{
	if (!iter) return;
	hoja_destruir(iter->hoja_actual, iter->arbol);
	cola_destruir(iter->hojas, (void (*)(void *, void *))hoja_destruir, (void *) iter->arbol);
	free(iter);
}
